package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-28
 */

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 */
public class NC14 {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        if (root==null) return new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode cur = queue.removeFirst();
                if (cur.left!=null) queue.addLast(cur.left);
                if (cur.right!=null) queue.addLast(cur.right);
                list.add(cur.val);
            }
            res.add(list);
            if (queue.isEmpty()) break;
            list.clear();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode cur = queue.removeLast();
                if (cur.right!=null) queue.addFirst(cur.right);
                if (cur.left!=null) queue.addFirst(cur.left);
                list.add(cur.val);
            }
            res.add(list);
        }
        return res;
    }
}

